
#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>

using namespace std;

const int dirs[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

vector<pair<int, int>> findShortestPathBFS(const vector<vector<int>>& maze) {
    if (maze.empty() || maze[0].empty()) return {};

    int m = maze.size();
    int n = maze[0].size();

    vector<vector<bool>> visited(m, vector<bool>(n, false));
    queue<pair<int, int>> q;
    unordered_map<int, pair<int, int>> parent; // 记录路径

    q.emplace(0, 0);
    visited[0][0] = true;
    parent[0] = {-1, -1}; // 起点无父节点

    while (!q.empty()) {
        auto [x, y] = q.front();
        q.pop();

        if (x == m - 1 && y == n - 1) {
            // 回溯路径
            vector<pair<int, int>> path;
            for (auto at = make_pair(x, y); at != make_pair(-1, -1); at = parent[at.first * n + at.second]) {
                path.emplace_back(at);
                int key = at.first * n + at.second;
                at = parent[key];
            }
            reverse(path.begin(), path.end());
            return path;
        }

        for (const auto& dir : dirs) {
            int nx = x + dir[0];
            int ny = y + dir[1];

            if (nx >= 0 && nx < m && ny >= 0 && ny < n && maze[nx][ny] == 0 && !visited[nx][ny]) {
                visited[nx][ny] = true;
                q.emplace(nx, ny);
                parent[nx * n + ny] = {x, y}; // 记录父节点
            }
        }
    }

    return {}; // 无解
}

int main() {
    vector<vector<int>> maze = {
        {0, 1, 0, 0},
        {0, 0, 0, 1},
        {1, 1, 0, 0},
        {0, 0, 0, 0}
    };

    vector<pair<int, int>> path = findShortestPathBFS(maze);

    if (path.empty()) {
        cout << "No path found!" << endl;
    } else {
        cout << "Shortest path (BFS):" << endl;
        for (const auto& p : path) {
            cout << "(" << p.first << ", " << p.second << ") ";
        }
        cout << endl;
    }

    return 0;
}